package bTree.LeetCode;

public class 交错字符串 {
    public boolean isInterleave(String s1, String s2, String s3) {
        int length1 = s1.length();
        int length2 = s2.length();
        int length3 = s3.length();
        if (length1+length2!=length3){
            return false;
        }
        //dp[i][j]的含义是s1的前i个字符和s2的前j个字符能否交错组成s3的前i+j个字符
        boolean [] []dp=new boolean[length1+1][length2+1];
        dp[0][0]=true;
        //s1填充的边界初始化
        for (int i=1;i<=length1;i++){
            dp[i][0]=dp[i-1][0]&&s1.charAt(i-1)==s3.charAt(i-1);
        }
        //s2填充的边界初始化
        for (int i=1;i<=length2;i++){
            dp[0][i]=dp[0][i-1]&&s2.charAt(i-1)==s3.charAt(i-1);
        }
        for (int i=1;i<=length1;i++){
            for (int j=1;j<=length2;j++){
                dp[i][j]=(dp[i-1][j]&&s1.charAt(i-1)==s3.charAt(i+j-1))||(dp[i][j-1]&&s2.charAt(j-1)==s3.charAt(i+j-1));
            }
        }
        return dp[length1][length2];
    }
}